#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int partition(int arr[], int starIndex, int endIndex)
{
	int pivot = arr[starIndex];
	int mark = starIndex;
	for (int i = starIndex + 1; i <= endIndex; i++)
	{
		if (pivot > arr[i])
		{
			mark++;
			int tmp = arr[mark];
			arr[mark] = arr[i];
			arr[i] = tmp;
		}
	}
	arr[starIndex] = arr[mark];
	arr[mark] = pivot;
	return mark;
}



void quickSort(int arr[], int starIndex, int endIndex)
{
	if (starIndex >= endIndex)
	{
		return;
	}
	int pivotIndex = partition(arr, starIndex, endIndex);
	quickSort(arr, starIndex, pivotIndex - 1);
	quickSort(arr, pivotIndex + 1, endIndex);
}

int main()
{
	int arr[] = { 4,6,8,5,7,2,1,9,3,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	quickSort(arr, 0, sz - 1);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}